METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)<br />Workshop on Expanders and derandomization (March 21-25, 2011)<br />Mar 21, 15:00-16:00 - Anup Rao (U. Washington, Seattle)<br />Pseudorandom generators for regular branching programs<br />----<br />We give new pseudorandom generators for regular read-once branching programs of small width.<br />A branching program is regular if the in-degree of every vertex in it is either 0 or 2. For every width d and length n, our pseudorandom generator uses a seed of length O((log d +log log n + log(1/epsilon )) log n) to produce n bits that cannot be distinguished from a uniformly random string by any regular width d length n read-once branching program, except with probability epsilon.<br /><br />We shall also discuss a simple argument that shows that the set of all binary strings with less than d non-zero entries forms a hitting set for regular width d branching programs.<br /><br />Joint work with Mark Braverman, Ran Raz and Amir Yehudayoff.
